var arr = [3, 5, 7, 1, 4, 56, 12, 37, 78, 25, 0, 9, 3, 8, 42];

function InversePairs(data) {
  return mergeSort(data, 0, data.length - 1, []);
}

function mergeSort(array, left, right, temp) {
  if (left < right) {
    const mid = parseInt((left + right) / 2);
    const l = mergeSort(array, left, mid, temp);
    const r = mergeSort(array, mid + 1, right, temp);
    // console.log(array, left, right, mid, temp)
    const m = merge(array, left, right, mid, temp);
    return l + m + r;
  } else {
    return 0;
  }
}


function merge(array, left, right, mid, temp) {
  let leftIndex = mid;
  let rightIndex = right;
  let tempIndex = right - left;
  let count = 0;
  while (leftIndex >= left && rightIndex > mid) {
    if (array[leftIndex] > array[rightIndex]) {
      // 左右两数组是排好顺序的
      // 若左侧一个数大于右测第n个数，则大于右侧0-n每个数
      count += rightIndex - mid;
      temp[tempIndex--] = array[leftIndex--];
    } else {
      temp[tempIndex--] = array[rightIndex--];
    }
  }
  while (leftIndex >= left) {
    temp[tempIndex--] = array[leftIndex--];
  }
  while (rightIndex > mid) {
    temp[tempIndex--] = array[rightIndex--];
  }
  console.log(temp);
  tempIndex = 0;
  for (let i = left; i <= right; i++) {
    array[i] = temp[tempIndex++];
  }
  return count;
}
// console.log(InversePairs(arr));

console.log(merge(arr, 0, 14, 7, []));
